The present invention relates in general to the field of virtual memory management and, more particularly, to a method for emulating the operation of a memory management unit.
Computers include general purpose central processing units (CPUs) that are designed to execute a specific set of system instructions. A group of processors that have similar architecture or design specifications may be considered to be members of the same processor family. Examples of current processor families include the Motorola 680xc3x970 processor family, manufactured by Motorola, Inc. of Phoenix, Arizona; the Intel 80xc3x9786 processor family, manufactured by Intel Corporation of Sunnyvale, Calif.; and the PowerPC processor family, which is manufactured by Motorola, Inc. and used in computers manufactured by Apple Computer, Inc. of Cupertino, Calif. Although a group of processors may be in the same family because of their similar architecture and design considerations, processors may vary widely within a family according to their clock speed and other performance parameters.
Each family of microprocessors executes instructions that are unique to the processor family. The collective set of instructions that a processor or family of processors can execute is known as the processor""s instruction set. As an example, the instruction set used by the Intel 80xc3x9786 processor family is incompatible with the instruction set used by the PowerPC processor family. The Intel 80xc3x9786 instruction set is based on the Complex Instruction Set Computer (CISC) format. The Motorola PowerPC instruction set is based on the Reduced Instruction Set Computer (RISC) format. CISC processors use a large number of instructions, some of which can perform rather complicated functions, but which require generally many clock cycles to execute. RISC processors use a smaller number of available instructions to perform a simpler set of functions that are executed at a much higher rate.
The uniqueness of the processor family among computer systems also typically results in incompatibility among the other elements of hardware architecture of the computer systems. A computer system manufactured with a processor from the Intel 80xc3x9786 processor family will have a hardware architecture that is different from the hardware architecture of a computer system manufactured with a processor from the PowerPC processor family. Because of the uniqueness of the processor instruction set and a computer system""s hardware architecture, application software programs are typically written to run on a particular computer system running a particular operating system.
A computer manufacturer will want to maximize its market share by having more rather than fewer applications run on the microprocessor family associated with the computer manufacturer""s product line. To expand the number of operating systems and application programs that can run on a computer system, a field of technology has developed in which a given computer having one type of CPU, called a host, will include an emulator program that allows the host computer to emulate the instructions of an unrelated type of CPU, called a guest. Thus, the host computer will execute an application that will cause one or more host instructions to be called in response to a given guest instruction. Thus, the host computer can both run software design for its own hardware architecture and software written for computers having an unrelated hardware architecture. As a more specific example, a computer system manufactured by Apple Computer, for example, may run operating systems and program written for PC-based computer systems. It may also be possible to use an emulator program to operate concurrently on a single CPU multiple incompatible operating systems. In this arrangement, although each operating system is incompatible with the other, an emulator program can host one of the two operating systems, allowing the otherwise incompatible operating systems to run concurrently on the same computer system.
When a guest computer system is emulated on a host computer system, the guest computer system is said to be a virtual machine, as the host computer system exists only as a software representation of the operation of the hardware architecture of the guest computer system. The terms emulator and virtual machine are sometimes used interchangeably to denote the ability to mimic or emulate the hardware architecture of an entire computer system. As an example, the Virtual PC software created by Connectix Corporation of San Mateo, Calif. emulates an entire computer that includes an Intel 80xc3x9786 Pentium processor and various motherboard components and cards. The operation of these components is emulated in the virtual machine that is being run on the host machine. An emulator program executing on the operating system software and hardware architecture of the host computer, such as a computer system having a PowerPC processor, mimics the operation of the entire guest computer system. The emulator program acts as the interchange between the hardware architecture of the host machine and the instructions transmitted by the software running within the emulated environment.
Because the size of application programs has increased over time and because there are operating advantages afforded to multitasking operating system environments, many computer systems employ a virtual memory system in which a large virtual address space is defined for each application program. The virtual memory is divided into blocks of memory known as pages. To accommodate the size of the virtual address space, a limited number of the virtual memory pages are mapped to short-term physical memory, such as dynamic RAM. The remainder of the virtual memory pages are mapped to long-term storage, such as hard disk drives. The division of virtual memory between short-term RAM storage and long-term hard disk storage is an aid to multitasking operating systems in that several programs can share the RAM memory of the system.
Virtual memory systems are implemented through the use of a page table, which is an indexed data structure that relates logical memory addresses to physical memory addresses. Because programs operating in a virtual memory system will access data locations according to their virtual memory address, the virtual memory address must be translated to a physical memory address to complete the read or write operation. The page table is used by the operating system to translate the virtual page address to a physical page address. A page table contains virtual to physical memory translations consisting of a virtual page number and a corresponding physical page number. Following the translation, the processor accesses the data using the physical page address.
Because tables are often stored in main memory, access to virtual memory is often time-consuming. Virtual memory requires two memory accesses to fetch a single entry from memory. The first access is to the page table and is made to map the virtual address to the physical address. After the physical address is known, a second access is required to fetch the data from physical memory. In an effort to speed up memory accesses, conventional microprocessors use a special purpose cache memory to store certain virtual to physical memory address translations. This cache is often referred to as a translation look-aside buffer (TLB). The number of virtual to physical memory translations in a TLB is typically smaller than the total number of translations in the page table. In operation, prior to seeking the translation of a of a virtual address from the page tables stored in main memory, a processor can first refer to the TLB to determine whether the physical address translation of the virtual address is stored in the TLB. If the translation of the virtual address to the physical address is stored in the TLB, the TLB outputs to the process the physical address and a time-consuming access to main memory is avoided.
Many emulator programs attempt to emulate the virtual memory operation of the guest hardware architecture and operating system. In this manner, the emulator application, which runs on the host operating system, emulates the operation of the guest hardware architecture and guest operating system. In an attempt to closely mimic the operation of the guest hardware architecture and operating system, the emulator program will attempt to mimic the manner in which the guest processor and operating system populate a page table and an emulated translation look-aside buffer. To provide full emulation, the emulation program must attempt to track the page tables established by the guest processor and guest operating system. The emulation program must also attempt to track the guest processor""s attempts to store address translations in an emulated translation look-aside buffer. Difficulties arise when the emulation program is faced with the task of unmapping certain address translations stored in a related page table maintained by the host computer system following commands issued by the guest processor and operating system.
The family of Intel 80xc3x9786 processors include commands to invalidate certain entries in the translation look-aside buffer. One such command invalidates a single entry in the translation look-aside buffer following a change to the physical location of a virtual memory address. Another command invalidates or flushes the entire content of the translation look-aside buffer following a significant number of changes to the address translations in the page table. The flush occurs often in those instances in which an 80xc3x9786 processor must switch between two competing multitasking processes. As the processor switches between multitasking processes, the processor may issue the TLB flush instruction.
For the emulation program, the difficulty of the TLB flush instruction is identifying the address translations in the page table maintained by the host system that must be unmapped. In the case of an instruction from an emulated 80xc3x9786 processor invalidating a single entry in the TLB, the emulation program can more easily identify the translation entry that must be unmapped. Unmapping address translations is substantially more difficult and time-consuming if the TLB flush instruction is given by the processor. According to known methods of compensating for a TLB flush instruction, the entire page table must be polled to make certain that none of the physical addresses identified for the virtual addresses in the page table have been modified. This process usually involves making a direct comparison between the contents of the virtual page table of the guest system and the page table maintained by the host operating system for use by the emulation program. The process of polling the entirety of the page table, although necessary in the case of a TLB flush instruction, is time-consuming. The emulation program also may face a difficult task in emulating the operation of the memory management unit of the guest operating system as the guest operating system transitions between memory access levels. The page table of a guest operating system may track, for each virtual memory address translation, the memory privilege level of the memory location. Some pages in memory may only be only accessed by privileged or system-level code of the operating system and may not be accessed by user-level code of the operating system. Other locations in memory may be accessed by system-level code in the guest operating system on read and write basis, while the same memory location may only be accessed by user-level code on a read-only basis. Thus, the guest operating system may attempt to track in its page tables the memory access levels of the memory locations identified in the page tables. It is typical that the host operating system will allow the emulation program to run with user-level privileges. It is also possible that the host operating system will have a different set of semantics or different format for its memory access levels and privileges. The host operating system will also seek to monitor those instances in which the guest operating system has transitioned between a more privileged memory access level and a less privileged memory access level. In this instance, the emulation program will seek to update any page table maintained in the host operating system to track the page table that is now accessible by the less privileged memory access level of the guest operating system. As in the case of TLB flush instruction, tracking the changes to the emulated page table of the guest operating system has proved difficult in view of the multiple memory access levels of a typical guest operating system and the ability of the guest operating system to transition between more privileged memory access levels and less privileged memory access levels.
In accordance with the present invention, a method is provided for altering the format of a text string that has populated a data field of a web-generated document or proof.
The present invention concerns a method for emulating the operation of a memory management unit. An emulator program tracks the changes to the page table of a guest computer system by maintaining a set of hierarchical lists of the memory locations accessed by the emulated computer system. An address translation for each memory location accessed by the guest computer system is placed on one of the hierarchical lists. In response to an action taken in the guest computer system resulting in a number of changes to the page table of the guest computer system, the entries in one or more of the hierarchical address translation lists are unmapped so that the content of the page table of the host computer system is similar to the content of the emulated page table of the guest computer system.
The technique disclosed herein is advantageous in that it improves the performance of emulated computer systems. When the host computer system makes a set of changes to its page table, the process of the present invention permits the host computer system to locate the address translations that must be unmapped for the physical page table of the host computer system to match the emulated page table of the guest computer system. In doing so, the process of the present invention avoids the technique of comparing the contents of the page table on an entry-by-entry basis.
The technique of the present invention is also advantageous in that it permits the hierarchical arrangement of the address translation lists maintained by the emulation program and the host computer system. The address translation lists are arranged such that the address translations that must be unmapped most frequently are grouped on a certain address translation list. A category of address translations that must be unmapped less frequently is placed on another list, and so on. When an action occurs in the guest computer system calling for the unmapping of the most frequently unmapped set of address translations, the address translations in the remaining lists of address translations are not unmapped. Rather, these translations remain in the page table of the host computer system until such time as an action occurs in the guest computer system that requires that this set of addresses be unmapped. In this manner, the lists of address translations can be selectively arranged so that they correspond to actions taken in the guest computer system, allowing the list of addresses to be unmapped in the host computer system according to a technique in which address translations are unmapped according to their unmapping frequency or relation to other address in the guest computer system.